﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Linq;

namespace TSP
{
	class Edge
	{
		public List<int> nodes;

		public Edge(int start, int end)
		{
			nodes = new List<int>();
			nodes.Add(start);
			nodes.Add(end);
		}

		public Edge(Edge first, Edge second)
		{
			if (first.nodes.Last() == second.nodes.First())
			{
				nodes = new List<int>(first.nodes);
				nodes.RemoveAt(nodes.Count - 1);
				nodes.AddRange(second.nodes);
			}
		}

		public ArrayList GetRoute(ref City[] cities)
		{
			ArrayList r = new ArrayList();
			foreach (int i in nodes) r.Add(cities[i]);
			return r;
		}
	}

	class Edges
	{
		private List<Edge> edges;

		public bool comp(int size)
		{
			return (edges.Count == 1 && edges[0].nodes.Count == size);
		}

		public Edges()
		{
			edges = new List<Edge>();
		}

		public Edges(Edges other)
		{
			edges = new List<Edge>(other.edges);
		}

		public void add(Edge e)
		{
			for (int i = 0; i < edges.Count; i++)
			{
				if (e.nodes.First() == edges[i].nodes.Last())
				{
					e = new Edge(edges[i], e);
					edges.RemoveAt(i);
					break;
				}
			}

			for (int i = 0; i < edges.Count; i++)
			{
				if (e.nodes.Last() == edges[i].nodes.First())
				{
					e = new Edge(e, edges[i]);
					edges.RemoveAt(i);
					break;
				}
			}
			edges.Add(e);
		}

		public bool checkCycle(Edge edge)
		{
			foreach (Edge e in edges)
			{
				if (e.nodes.First() == edge.nodes.Last() && e.nodes.Last() == edge.nodes.First()) return true;
			}
			return false;
		}

		public ArrayList GetRoute(ref City[] cities)
		{
			return edges[0].GetRoute(ref cities);
		}
	}

	class CostMatrix
	{
		private int size;
		private double[,] matrix;
		public double costSoFar;
		Edges usededges;
		public bool comp;

		public CostMatrix(CostMatrix parent)
		{
			this.size = parent.size;
			this.costSoFar = parent.costSoFar;
			this.matrix = new double[size, size];
			Array.Copy(parent.matrix, this.matrix, this.size * this.size);
			this.usededges = new Edges(parent.usededges);
			this.comp = parent.comp;
		}

		public CostMatrix(ref City[] cities)
		{
			size = cities.Length;
			matrix = new double[size, size];
			usededges = new Edges();
			comp = false;
			costSoFar = 0;
			buildMatrix(cities);
			reduceMatrix();
		}

		private void buildMatrix(City[] cities)
		{
			for (int i = 0; i < cities.Length; i++)
			{
				for (int j = 0; j < cities.Length; j++)
				{
					if (i == j)
					{
						matrix[i, j] = double.PositiveInfinity;
					}
					else
					{
						matrix[i, j] = cities[i].costToGetTo(cities[j]);
					}
				}
			}
		}

		public MatrixPairs getIncExc()
		{
			int row = -1;
			int col = -1;
			double minimum = double.PositiveInfinity;
			double maximum = 0;

			for (int i = 0; i < size; i++)
			{
				for (int j = 0; j < size; j++)
				{
					if (matrix[i, j] == 0)
					{
						if (!(usededges.checkCycle(new Edge(i, j)) && !usededges.comp(size)))
						{
							double include = costSoFar;

							for (int x = 0; x < size; x++)
							{
								if (x != j)
								{
									double min = double.PositiveInfinity;

									for (int y = 0; y < size; y++)
									{
										if (y != i)
										{
											if (matrix[y, x] < min) min = matrix[y, x];
										}
									}
									include += min;
								}
							}

							double exclude = costSoFar;

							double min1 = double.PositiveInfinity;
							for (int k = 0; k < size; k++)
							{
								if (k != i)
								{
									if (matrix[k, j] < min1) min1 = matrix[k, j];
								}
							}
							exclude += min1;

							min1 = double.PositiveInfinity;
							for (int k = 0; k < size; k++)
							{
								if (k != j)
								{
									if (matrix[i, k] < min1) min1 = matrix[i, k];
								}
							}
							exclude += min1;

							if (include <= minimum && exclude >= maximum)
							{
								row = i;
								col = j;
								minimum = include;
								maximum = exclude;
							}
						}
					}
				}
			}

			return makeIncExc(row, col);
		}

		private MatrixPairs makeIncExc(int row, int col)
		{
			MatrixPairs incexc = null;
			if (row != -1)
			{
				incexc = new MatrixPairs();
				incexc.include = new CostMatrix(this);
				for (int i = 0; i < size; i++)
				{
					incexc.include.matrix[i, col] = double.PositiveInfinity;
					incexc.include.matrix[row, i] = double.PositiveInfinity;
				}

				if (!usededges.comp(size)) incexc.include.usededges.add(new Edge(row, col));
				else incexc.include.comp = true;
				incexc.include.reduceMatrix();

				incexc.exclude = new CostMatrix(this);
				incexc.exclude.matrix[row, col] = double.PositiveInfinity;
				incexc.exclude.reduceMatrix();
			}

			return incexc;
		}

		public ArrayList GetRoute(ref City[] cities)
		{
			return usededges.GetRoute(ref cities);
		}

		private void reduceMatrix()
		{
			for (int i = 0; i < size; i++)
			{
				double min = double.PositiveInfinity;

				for (int j = 0; j < size; j++) if (matrix[i, j] < min) min = matrix[i, j];

				if (!double.IsPositiveInfinity(min))
				{
					for (int j = 0; j < size; j++) matrix[i, j] -= min;
					costSoFar += min;
				}
				double min2 = double.PositiveInfinity;

				for (int j = 0; j < size; j++) if (matrix[j, i] < min2) min2 = matrix[j, i];

				if (!double.IsPositiveInfinity(min2))
				{
					for (int j = 0; j < size; j++) matrix[j, i] -= min2;
					costSoFar += min2;
				}
			}
		}
	}

	class MatrixPairs
	{
		public CostMatrix include;
		public CostMatrix exclude;

		public MatrixPairs()
		{
			include = null;
			exclude = null;
		}
	}
}